#include <iostream>
#include <time.h>

using namespace std;
#define MAX 20//于表头的前驱和表尾的后继都不存放元素，所以实际能存放的有效元素个数比MAX少2个
#define Null -1
int head=Null,Free=0;
int j=0;int n=0;
struct List
{
    int next[MAX];
    int key[MAX];
    int prev[MAX];
};

int isIn(int *num,int index,int pat)//生成的随机数pat是否已经存在
{
    int i=0;
    for(i=0;i<index;++i)
        if(pat==num[i])
            return 1;
        return 0;   
}

int RAND(int *num)//随机抽取元素互异的key 这样key不会出现重复数值，易于以后的删除工作。
{
    int result=0;
    if (j>=MAX)
    {
        return Null;
    }
    while(1)
    {
        result=rand()%MAX;
        if(!isIn(num,j,result))
        {
            num[j]=result;
            j++;
            break;
        }
    }
    return result;
}
//链表初始化
void Initialization(struct List &T,int*num)
{
   Free=RAND(num);//[1,MAX-1]之间的数随机选择一个作为表头元素下标
   for (int i=0;i<MAX;i++)
   {
       T.key[i]=0;
       T.prev[i]=0;
   }
   int p=Free;
   for ( int i=0;i<MAX-1;i++)
   {
       p=T.next[p]=RAND(num);
   }
   T.next[p]=Null;//链表最后的next指针为空。-1代表空
   j=0;//结构体T初始化后，临时数组num下标设置为0.
}  
//分配空间
int Allocate_object(struct List &T,int*num)
{
    if (Free==Null)
    {
        cerr<<"out of space!"<<endl;
        return Null;
    }
    else
    {    
      int x=Free; 
	  Free=T.next[x];
      return x;
    }
}
//释放空间
void Free_object(struct List &T,int x)
{
   T.next[x]=Free;
   Free=x;
   n--;
}
//插入数据
void insert(struct List &T,int k,int *num)
{
     int x=Allocate_object(T,num);//类似指针开辟一段内存空间
	 if (x==Null)
	 {
		 return;
	 }
	 T.next[x]=head;
	 T.key[x]=k;
	 if (head!=Null)
	 {
		 T.prev[head]=x;
	 }
	 head=x;
	 T.prev[x]=Null;
     n++;
}
//查找数据
int search(struct List &T,int k)
{
   int t=head;
   if (head==Null)
   {
       cout<<"链表为空！无法查找！"<<endl;
       return Null;
   }
   while (t!=-1&&T.key[t]!=k)
   {
       t=T.next[t];
   }
   if (t==Null)
   {
       cout<<"不存在这个数据！"<<endl;
       return Null;
   } 
   else
   {
      cout<<"待查找数据已经找到！"<<endl;
      return t;//将待删除的数据下标返回，易于删除工作。
   }
}
//删除数据
void Delete(struct List &T,int k)//删除特定值的删除函数
{ 
    int p=0;
        p=search(T,k);
        if (p!=Null)
        {
       
            if (T.prev[p]!=Null)
            {
                T.next[T.prev[p]]=T.next[p];
            } 
            else
            {
                head=T.next[p];
            }
            if (T.next[p]!=Null)
            {
                T.prev[T.next[p]]=T.prev[p];
            }
			T.key[p]=0;//设置为0做为一个标志，表明这个位置为空。完全可以设置其他数字作为标志。这里的0起到的是标志符号作用
            cout<<"删除成功！"<<endl;
            Free_object(T,p);
        } 
        else
        {
            cout<<"待删除的数据不存在！无法删除！"<<endl;
        }
}
void Compactify_list(struct List &T)
{
	int i=0,k=0;
	int temp[MAX]={0};
	while (i!=n)//O(n)
	{
		if (T.key[i]==0)//由于删除后，我们把其设置为0这个标志，那么根据标志判断前n个位置哪些是空的，哪些是非空的。
		{
           temp[k]=i;//如果是空值，那么记录下来保存到临时数组中。
		   k++;
		}
		i++;
	}
	int p=head,j=0;
	while (p!=Null)//O(n)
	{
		if (p>=n)
		{
			T.key[temp[j]]=T.key[p];
			T.next[temp[j]]=T.next[p];
			T.prev[temp[j]]=T.prev[p];
			T.prev[T.next[temp[j]]]=temp[j];
			T.next[T.prev[temp[j]]]=temp[j];
			if (head==p)
			{
				head=temp[j];
			}
			j++;
		}
        p=T.next[p];
	}
}
void Print(struct List &T)
{
    int i=head;
    if (head==Null)
    {
        cout<<"此链表为空！"<<endl;
        return;
    }
    while (i!=Null)
    {
        cout<<T.key[i]<<"->";
        i=T.next[i];
    }
    cout<<endl;
}

int  main()
{
    struct List T;
    srand((unsigned)time(NULL));
    int num[MAX]={0};//临时存放next[MAX]和key[MAX]数组的值，目的是用于生成互异的随机数
    cout<<"初始化链表中。"; 
    Initialization(T,num);
    Print(T);
    cout<<"给链表添加数据中。"; 
    insert(T,35,num);
	insert(T,53,num);
	insert(T,65,num);
	insert(T,78,num);
    insert(T,13,num);
	insert(T,2,num);
	insert(T,5,num);
	insert(T,7,num);
	insert(T,18,num);
	insert(T,15,num);
    Print(T);
    cout<<"查找数据中。"; 
    search(T,53);
    cout<<"删除数据中。"; 
    Delete(T,65);
    Delete(T,2);
	Delete(T,5);
	Delete(T,500);
	Delete(T,78);
	insert(T,25,num);
	Print(T);
	Compactify_list(T);
	Print(T);
}
